//
// Created by pzw on 24-3-15.
//

#include "FindSort.h"

/**
 * 1. **List**：一个模板模板参数，它自身是一个模板，这个模板至少需要两个模板参数：一个是类型参数（ typename ），
 *             另一个是参数包（ typename... ），可以接受一个或多个额外的模板参数。
 *             这允许 List 匹配那些至少需要两个模板参数的模板，比如标准库中的 std::vector ，它有一个类型参数和一个分配器参数。
 * 2. **Tp**：一个类型参数，通常用于指定容器中元素的类型。
 *
 * @tparam List - 任意容器
 * @tparam Tp   - 容器中的任意类型
 * @param lst   - 被排序后的容器实例
 */
template<template<typename, typename ...> class List, typename Tp>
void FindSort::std_sort_list(List<Tp> &lst) {
    using namespace std;
    // 将lst的元素复制到vector中
    vector<Tp> v(lst.begin(), lst.end());
    // 对vector进行排序
    sort(v.begin(), v.end());
    // 清空原列表
    lst.clear();
    // 将排序后的元素复制回lst
    copy(v.begin(), v.end(), back_inserter(lst));
}

/**
 * 1. **List**：一个模板模板参数，它自身是一个模板，这个模板可以接受任意数量的模板参数（通过参数包 typename ... 表示）。
 *             这意味着 List 可以是任何模板，无论它需要多少个模板参数，都可以匹配。
 * 2. **Tp**：一个类型参数，通常用于指定容器中元素的类型。
 *
 * @tparam List - 任意容器
 * @tparam Tp   - 容器中的任意类型
 * @param lst   - 被排序后的容器实例
 */
template<template<typename ...> class List, typename Tp>
void FindSort::std_sort_list2(List<Tp> &lst) {
    using namespace std;
    // 将lst的元素复制到vector中
    vector<Tp> v(lst.begin(), lst.end());
    // 对vector进行排序
    sort(v.begin(), v.end());
    // 清空原列表
    lst.clear();
    // 将排序后的元素复制回lst
    copy(v.begin(), v.end(), back_inserter(lst));
}

void FindSort::std_partial_sort_copy(const std::vector<Book> &sales) {
    using namespace std;
    vector<Book> bestsellers(10);
    partial_sort_copy(
            sales.begin(), sales.end(),
            bestsellers.begin(), bestsellers.end(),
            [](const Book &b1, const Book b2) -> bool {
                return b1.copies_sold() > b2.copies_sold();
            }
    );
}

template<typename Tp, typename Compare>
void FindSort::std_binary_search(const std::vector<Tp> &vs, const Tp &target, Compare comp) {
    if (std::binary_search(vs.begin(), vs.end(), target, comp)) {
        target << (std::cout << "std_binary_search: found target == ") << std::endl;
    } else {
        std::cout << "std_binary_search: target not found" << std::endl;
    }
}

template<typename Tp>
void FindSort::std_binary_search2(const std::vector<Tp> &vs, const Tp &target) {
    if (std::binary_search(vs.begin(), vs.end(), target)) {
        std::cout << "std_binary_search: found target == " << target << std::endl;
    } else {
        std::cout << "std_binary_search: target not found" << std::endl;
    }
}

template<typename Tp, typename Tp2>
void FindSort::std_merge_vector_list(std::vector<Tp> &vs, std::list<Tp2> lst) {
    using namespace std;
    sort(vs.begin(), vs.end());
    lst.sort();
    vector<Tp2> v2;
    merge(vs.begin(), vs.end(), lst.begin(), lst.end(), back_inserter(v2));
    for (auto it = v2.begin(); it != v2.end(); it++) {
        cout << *it << ", ";
    }
    cout << endl;
}

template<typename Tp, typename Tp2>
void FindSort::std_merge_vector_list2(std::vector<Tp> &vs, std::list<Tp2> lst) {
    using namespace std;
    sort(vs.begin(), vs.end());
    lst.sort();
    vector<Tp2> v2;
    merge(vs.begin(), vs.end(), lst.begin(), lst.end(), back_inserter(v2));
    for (auto it = v2.begin(); it != v2.end(); it++) {
        (*it) << (cout) << ", " << endl;
    }
}

void FindSort::std_set_union_diff(std::string s1, std::string s2) {
    using namespace std;
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());

    string s3(s1.size() + s2.size(), '*');
    cout << s3 << endl;

    auto up = set_union(
            s1.begin(), s1.end(),
            s2.begin(), s2.end(),
            s3.begin()
    );
    cout << s3 << endl;
    for (auto p = s3.begin(); p != up; ++p) {
        cout << *p;
    }
    cout << endl;

    s3.assign(s1.size() + s2.size(), '+');
    up = set_difference(
            s1.begin(), s1.end(),
            s2.begin(), s2.end(),
            s3.begin()
    );
    cout << s3 << endl;
    for (auto p = s3.begin(); p != up; ++p) {
        cout << *p;
    }
    cout << endl;
}

void FindSort::std_heap_func(std::string s) {
    using namespace std;
    make_heap(s.begin(), s.end());
    pop_heap(s.begin(), s.end());
    pop_heap(s.begin(), s.end() - 1);
    pop_heap(s.begin(), s.end() - 2);

    *(s.end() - 3) = 'f';
    push_heap(s.begin(), s.end() - 2);
    *(s.end() - 2) = 'x';
    push_heap(s.begin(), s.end() - 1);
    *(s.end() - 1) = 'y';
    push_heap(s.begin(), s.end());
    sort_heap(s.begin(), s.end());
    reverse(s.begin(), s.end());
}

template<typename Tp, typename Tp2>
bool FindSort::std_lexicographical_compare(Tp tp, Tp2 tp2) {
    using namespace std;
    bool compare = lexicographical_compare(
            tp.begin(), tp.end(),
            tp2.begin(), tp2.end()
    );
    return compare;
}

int FindSort_main() {
    std::list<int> lst{0, 7, 2, 3, 5, 4, 6, 1};
    FindSort::std_sort_list<std::list, int>(lst);
    for (auto it = lst.begin(); it != lst.end(); it++) {
        std::cout << "FindSort_main: std_sort_list, lst = " << *it << std::endl;
    }

    std::list<int> lst2{0, 7, 2, 3, 5, 4, 6, 1};
    FindSort::std_sort_list2<std::list, int>(lst2);
    for (auto it = lst2.begin(); it != lst2.end(); it++) {
        std::cout << "FindSort_main: std_sort_list2, lst2 = " << *it << std::endl;
    }

    std::vector<Book> v{10};
    for (int i = 0; i < 10; ++i) {
        auto x = rand() % 1000L;
        v.push_back(Book(x));
    }
    FindSort::std_partial_sort_copy(v);
    for (auto it = v.begin(); it != v.end(); it++) {
        std::cout << "FindSort_main: std_sort_list2, v = " << it->toString() << std::endl;
    }

    /* 自定义类型Book比较 */
    const Book &book = Book(100L);
    v.push_back(book);
    FindSort::std_binary_search<Book>(v, book);
    /* 原生基础类型比较 */
    std::vector<int> vec_int;
    FindSort::std_binary_search2<int>(vec_int, 7);

    std::vector<int> v_merge{3, 1, 4, 2};
    std::list<double> lst_merge{0.5, 2, 1.5, 2.5};
    FindSort::std_merge_vector_list(v_merge, lst_merge);
    std::vector<Book> v_merge2{Book(3L), Book(1L), Book(4L), Book(2L)};
    std::list<Book> lst_merge2{Book(0.5), Book(2L), Book(1.5), Book(2.5)};
    FindSort::std_merge_vector_list2(v_merge2, lst_merge2);

    std::string s1 = "qwertyasdfgzxcvb";
    std::string s2 = "poiuyasdfg.,mnb";
    FindSort::std_set_union_diff(s1, s2);

    std::string s = "herewego";
    FindSort::std_heap_func(s);

    std::string n1{"10000"};
    std::string n2{"999"};
    bool b1 = FindSort::std_lexicographical_compare(n1, n2);
    std::cout << "FindSort_main: b1 = " << b1 << std::endl;
    n1 = "Zebra";
    n2 = "Aardvark";
    bool b2 = FindSort::std_lexicographical_compare(n1, n2);
    std::cout << "FindSort_main: b2 = " << b2 << std::endl;

    return 0;
}

